# 方法一，数学，组合数
"""
核心思想：
从 (0, 0) 到 (m-1, n-1) 需要移动 (m-1) 次向下和 (n-1) 次向右，总步数为 (m+n-2) 步。
问题转化为：从 (m+n-2) 步中选 (m-1) 步向下（或 (n-1) 步向右），即组合数 C(m+n-2, m-1)。
"""
import math

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # comb 计算组合数
        return math.comb(m + n - 2, m - 1)

# 方法二：动态规划
"""
核心思想：
用 dp[i][j] 表示从 (0, 0) 到 (i, j) 的路径数，状态转移方程为：
dp[i][j] = dp[i-1][j] + dp[i][j-1]。
"""
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1] * n for _ in range(m)]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[m-1][n-1]

# 方法三：记忆化搜索
"""
当前元素，去下 or 右 的总和 
"""
from functools import cache

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        @cache
        def dfs(i, j):
            if i == m-1 or j == n-1:  # 用 or：只要机器人走到最后一行或最后一列，就只剩一条路径（只能向右或向下直走到底）。
                return 1
            return dfs(i+1, j) + dfs(i, j+1)
        return dfs(0, 0)
